preorder = [3, 9, 20, 15, 7]
inorder = [9, 3, 15, 20, 7]


class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

    def __iter__(self):
        return self.next()

    def next(self):
        yield self.val

        if self.left is not None:
            yield from iter(self.left)
        else:
            yield None

        if self.right is not None:
            yield from iter(self.right)
        else:
            yield None

    def __repr__(self):
        return str(self.val)


def build(preorder, inorder, start, end, root_index):
    if start > end:
        return None
    root = preorder[root_index[0]]
    root_index[0] += 1
    if start == end:
        return TreeNode(root)
    position = inorder.index(root)
    left = build(preorder, inorder, start, position - 1, root_index)
    right = build(preorder, inorder, position + 1, end, root_index)
    return TreeNode(root, left, right)


t = build(preorder, inorder, 0, len(preorder) - 1, [0])
print([node for node in t])
